// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-13 23:59
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
    ArrayList<String> ans = new ArrayList<>();

    /**
     * 生成有效括号序列
     */
    public List<String> generateParenthesis(int n) {
        // 朴素匹配
        /*
            1 第一个符号肯定是左括号
            2 最后一个括号肯定是右括号
            3 中间位置每一个位置有两种可能 -> 可是使用动态规划的递归实现 -> 结果列表作为参数传入或者作为全局变量
         */
        // 状态方程；用于记录当前状态(前面的左括号数)
//        int[] dp = new int[n];
//        dp[0] = 1;
        StringBuilder builder = new StringBuilder("(");
        int dp = 1;
        int lBracket = n - 1, rBracket = n;
        int i = 1;
        fillBracket(builder, dp, lBracket, rBracket);
        return ans;
    }

    /**
     * 填补括号方法，并将符合条件的方法填入ans列表中
     *
     * @param builder  用于字符串的添加
     * @param dp       状态变量
     * @param lBracket 左括号数量
     * @param rBracket 右括号数量
     */
    private void fillBracket(StringBuilder builder, int dp, int lBracket, int rBracket) {
//        if (lBracket > rBracket) {
//            // 当前右括号数量为0，无法进行填充
//            // 左括号数量大于右括号数量也无法填充
//            return;
//        }
        if (lBracket == 0 && rBracket == 0 && dp == 0) {
            ans.add(builder.toString());
            return;
        }

        if (dp == 0 && lBracket > 0) {
            builder.append('(');
            fillBracket(builder, dp + 1, lBracket - 1, rBracket);
            builder.deleteCharAt(builder.length() - 1);
        }
        if (dp > 0) {
            if (rBracket > 0) {
                builder.append(')');
                fillBracket(builder, dp - 1, lBracket, rBracket - 1);
                builder.deleteCharAt(builder.length() - 1);
            }
            if (lBracket > 0) {
                builder.append('(');
                fillBracket(builder, dp + 1, lBracket - 1, rBracket);
                builder.deleteCharAt(builder.length() - 1);
            }
        }
    }


    @Test
    public void shout() {
        int n = 3;
        System.out.println(generateParenthesis(3));
    }
}
